#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
int mi=0x3f3f3f3f;

void dfs(int sum,int st)
{
	if(sum==0)
	{
		mi=min(mi,st);
		return;
	}
	int a=sqrt(sum);
	if(sum>=a*a)
	{
		dfs(sum-a*a,st+1);
	}

	int b=cbrt(sum);
	if(sum>=b*b*b)
	{
		dfs(sum-b*b*b,st+1);
	}

}
void work()
{
	cin>>n;
	mi=0x3f3f3f3f;
	dfs(n,0);

	cout<<mi<<'\n';


	
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int _; 
	cin>>_;
	while (_--) work();
	return 0;
}